package main

import (
	"fmt"
)

/*
滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
*/
//自己想的 会超时
func maxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 {
		return []int{0}
	}
	var res []int
	var window []int
	//创建滑动窗口
	window = nums[:k]
	n := window[0]
	//遍历找出滑动窗口中的最大值
	for _, v := range window {
		if n < v {
			n = v
		}
	}
	//将最大值添加至结果集
	res = append(res, n)
	//循环遍历所有值
	for i := 0; i < len(nums)-k; i++ {
		window = append(window[1:], nums[k+i])
		m := window[0]
		for _, v := range window {
			if m < v {
				m = v
			}
		}
		res = append(res, m)
	}
	return res
}

//单调队列
/*
// 封装单调队列的方式解题
type MyQueue struct {
    queue []int
}

func NewMyQueue() *MyQueue {
    return &MyQueue{
        queue: make([]int, 0),
    }
}

func (m *MyQueue) Front() int {
    return m.queue[0]
}

func (m *MyQueue) Back() int {
    return m.queue[len(m.queue)-1]
}

func (m *MyQueue) Empty() bool {
    return len(m.queue) == 0
}

func (m *MyQueue) Push(val int) {
    for !m.Empty() && val > m.Back() {
        m.queue = m.queue[:len(m.queue)-1]
    }
    m.queue = append(m.queue, val)
}

func (m *MyQueue) Pop(val int) {
    if !m.Empty() && val == m.Front() {
        m.queue = m.queue[1:]
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    queue := NewMyQueue()
    length := len(nums)
    res := make([]int, 0)
    // 先将前k个元素放入队列
    for i := 0; i < k; i++ {
        queue.Push(nums[i])
    }
    // 记录前k个元素的最大值
    res = append(res, queue.Front())

    for i := k; i < length; i++ {
        // 滑动窗口移除最前面的元素
        queue.Pop(nums[i-k])
        // 滑动窗口添加最后面的元素
        queue.Push(nums[i])
        // 记录最大值
        res = append(res, queue.Front())
    }
    return res
}
*/

func main() {
	nums := []int{1, 5, 4, 3, 4, 5, 6, 7}
	k := 3
	fmt.Println(maxSlidingWindow(nums, k))
}
